package com.fan.prim;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 普利姆算法实践，修路问题
 * @author 19252
 */
public class PrimDemo {

    public static void main(String[] args) {
        PrimGraph graph = new PrimGraph(7);
        char[] vertexArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        graph.setVertexArray(vertexArray);
        // 为图添加边
        graph.setEdge(0, 1, 5);
        graph.setEdge(0, 2, 7);
        graph.setEdge(0, 6, 2);
        graph.setEdge(1, 0, 5);
        graph.setEdge(1, 3, 9);
        graph.setEdge(1, 6, 3);
        graph.setEdge(2, 0, 7);
        graph.setEdge(2, 4, 8);
        graph.setEdge(3, 1, 9);
        graph.setEdge(3, 5, 4);
        graph.setEdge(4, 2, 8);
        graph.setEdge(4, 5, 5);
        graph.setEdge(4, 6, 4);
        graph.setEdge(5, 3, 4);
        graph.setEdge(5, 4, 5);
        graph.setEdge(5, 6, 6);
        graph.setEdge(6, 0, 2);
        graph.setEdge(6, 1, 3);
        graph.setEdge(6, 4, 4);
        graph.setEdge(6, 5, 6);
        graph.showGraph();

        // 生成最小生成树
        MinTree.createMinTree(graph);
    }
}

/**
 * 最小生成树
 */
class MinTree {

    /**
     * 传入一个图对象，生成它的最小生成树
     * @param graph 图
     */
    public static void createMinTree(PrimGraph graph){
        createMinTree(graph, 0);
    }

    /**
     * 从图的指定顶点开始生成最小生成树
     * @param graph 图
     * @param vertex 图的指定顶点
     */
    public static void createMinTree(PrimGraph graph, int vertex){
        // 创建两个集合来帮助遍历顶点
        // vertexList 未遍历的顶点集合
        ArrayList<Integer> vertexList = new ArrayList<>();
        // tempVertexList 已经遍历的顶点集合
        ArrayList<Integer> tempVertexList = new ArrayList<>();
        // 首先将图中所有的顶点放入未遍历的顶点集合
        for (int i = 0; i < graph.getVertexNum(); i++) {
            vertexList.add(i);
        }
        // 指定的初始遍历顶点放入已经遍历的顶点集合
        tempVertexList.add(vertex);
        // 在未遍历的顶点集合移除指定的顶点
        vertexList.remove(vertex);
        // 临时变量
        int tempVertex1;
        int tempVertex2;
        // 保存已经遍历过的顶点
        int tempVertex3 = 0;
        // 保存还未遍历的顶点在集合中的下标
        int tempVertex4 = 0;
        // 临时变量不可达
        int tempMinWeight = graph.getUnreachable();
        // 普利姆算法生成的最小生成树的边是图中顶点的个数-1
        // n - 1
        for (int i = 1; i < graph.getVertexNum(); i++) {
            // 外层遍历已经遍历过的顶点
            // 1 , 2, 3, ..., n - 1
            for (int j = 0; j < tempVertexList.size(); j++) {
                // 获取遍历的顶点编号
                tempVertex1 = tempVertexList.get(j);
                // 内层遍历未遍历过的顶点
                // n - 1, n - 2, ... 1
                for (int k = 0; k < vertexList.size(); k++) {
                    // 获取未遍历过的顶点编号
                    tempVertex2 = vertexList.get(k);
                    // 比较已经遍历过的顶点与还未遍历的顶点之间的最小距离
                    if (graph.getData()[tempVertex1][tempVertex2] < tempMinWeight){
                        tempMinWeight = graph.getData()[tempVertex1][tempVertex2];
                        tempVertex3 = tempVertex1;
                        // 保存下标，方便移除
                        tempVertex4 = k;
                    }
                }
            }
            // (n - 1)[1 * (n - 1) + 2 * (n - 2) + ... + (n - 2) * 2 + (n - 1) * 1]
            // (n - 1)[2 * ( 1 * (n - 1) + 2 * (n - 2)) + ... + n / 2 * (n  - n / 2)]
            System.out.println(graph.getVertexArray()[tempVertex3] + "::" + graph.getVertexArray()[vertexList.get(tempVertex4)]
                    + "::weight = " + graph.getData()[tempVertex3][vertexList.get(tempVertex4)]);
            // 临时变量重置
            tempMinWeight = graph.getUnreachable();
            // 加入已遍历
            tempVertexList.add(vertexList.get(tempVertex4));
            // 从未遍历中移除
            vertexList.remove(tempVertex4);
        }
    }

}

/**
 * 图
 */
class PrimGraph {

    /**
     * 图中顶点的个数
     */
    private int vertexNum;

    /**
     * 图中的顶点
     */
    private char[] vertexArray;

    /**
     * 邻接矩阵
     */
    private int[][] data;

    /**
     * 标记图中对应下标的顶点是否被访问过
     */
    private boolean[] isVisited;

    /**
     * unreachable 不可达
     * unreachable 定义为一个非常大的值
     * 表示两点之间不连通
     */
    private int unreachable = Integer.MAX_VALUE;

    public PrimGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        data = new int[vertexNum][vertexNum];
        isVisited = new boolean[vertexNum];
        // 默认图中所有的点不可达
        for (int i = 0; i < vertexNum; i++) {
            Arrays.fill(data[i], unreachable);
        }
    }

    /**
     * 为图填充数据，设置图中两点的距离
     * @param vertex1 顶点
     * @param vertex2 顶点
     * @param weight  两个连接的顶点间的权值（在这里就是两点间的距离）
     */
    public void setEdge(int vertex1, int vertex2, int weight){
        data[vertex1][vertex2] = weight;
    }

    public void showGraph(){
        for (int[] vertexLink : data){
            System.out.println(Arrays.toString(vertexLink));
        }
    }

    public int getVertexNum() {
        return vertexNum;
    }

    public void setVertexNum(int vertexNum) {
        this.vertexNum = vertexNum;
    }

    public char[] getVertexArray() {
        return vertexArray;
    }

    public void setVertexArray(char[] vertexArray) {
        this.vertexArray = vertexArray;
    }

    public int[][] getData() {
        return data;
    }

    public void setData(int[][] data) {
        this.data = data;
    }

    public int getUnreachable() {
        return unreachable;
    }

    public void setUnreachable(int unreachable) {
        this.unreachable = unreachable;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }
}